package com.hot100.mid;

import java.util.Arrays;

/**
 * @author zhengTao
 * @version 1.0
 * @description:  最长递增子序列,动态规划经典题目
 * @date 2022/10/8 16:37
 */
public class Demo47 {


    public static void main(String[] args) {
        int[]  nums=new int[]{};
        int result = lengthOfLIS(nums);
        System.out.println(result);

    }

    public static int lengthOfLIS(int[] nums) {
        int n = nums.length;
        //初始化dp数组,dp[i]代表节点i结尾的最长子序列长度
        int[] dp = new int[n];
        //dp[i]至少是1
        Arrays.fill(dp, 1);
        for (int i = 0; i < n; i++) {
            //遍历dp[i]之前的元素
            for (int j = 0; j < i; j++) {
                //如果nums[i] > nums[j]说明i可以与j组成递增子序列，则取nums[j] + 1和nums[i]的最大值不断更新nums[i]
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int res = 0;
        //遍历dp数组求最长递增子序列长度
        for (int i = 0; i < n; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
